package net.sf.nlp.ltag.parser;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

import org.apache.log4j.Logger;

import net.sf.nlp.ltag.data.ArrayKey;
import net.sf.nlp.ltag.data.LTAGNode;
import net.sf.nlp.ltag.data.LTAGTree;
import net.sf.nlp.ltag.data.Operator;
import net.sf.nlp.ltag.data.Word;
import net.sf.nlp.ltag.data.LTAGTree.TreeType;
import net.sf.nlp.ltag.parser.LTAGState;
import net.sf.nlp.ltag.util.LTAG;

public abstract class ParserAlgAbstract implements ParserAlg {
	
	protected static Logger logger =  Logger.getLogger(ParserAlgAbstract.class);
	protected List<Word> words;
	protected AtomicInteger stateCount = null;
	
	private Map<String, List<LTAGTree>> ltagMap;
	private List<List<LTAGTree>> candidateTrees;
	
	private Map<ArrayKey, PriorityQueue<LTAGState>> statisticMap = new HashMap<ArrayKey, PriorityQueue<LTAGState>>();
	private Map<Object, Operator> cacheOperator = new ConcurrentHashMap<Object, Operator>();
	
	protected int bestResutCount;
	private int filterBestCount = 0;
	
	public ParserAlgAbstract(Map<String, List<LTAGTree>> ltagMap)
	{
		this.ltagMap = ltagMap;
	}
	
	public abstract List<ParserTree> calculate() throws Exception;
	
	public List<ParserTree> calculate(List<Word> words) throws Exception
	{
		this.words = words;
		
		init();
		
		return calculate();
	}
	
	private void init()
	{
		bestResutCount = Integer.valueOf(LTAG.ltagProperties.getProperty("BEST_RESULT_COUNT", "1"));
		filterBestCount = Integer.valueOf(LTAG.ltagProperties.getProperty("FILTER_BEST_COUNT", "6"));
		
		stateCount = new AtomicInteger(0);
		statisticMap.clear();
		cacheOperator.clear();
	}

	public abstract LTAGState generateLTAGState(LTAGTree tree, LTAGState state, int step);
	
	protected List<LTAGState> getInitStateSet() throws Exception
	{
		matchTree4Word(words);
		candidateTrees = findInitCandidateTrees(words);
		List<LTAGState> initStateSet = findInitLTAGStateSet(words, candidateTrees);
		
		//if (filterBestCount > 0)
		//	filterStateSetByPossibiltiy(initStateSet, false);
		
		return initStateSet;
	}
	
	private void filterStateSetByPossibiltiy(List<LTAGState> stateSet)
	{
		Iterator<LTAGState> i = stateSet.iterator();
		
		while(i.hasNext())
			validateStatistic(i.next(), filterBestCount);
		
		i = stateSet.iterator();
		
		while(i.hasNext())
		{
			LTAGState state = i.next();
			PriorityQueue<LTAGState> states = statisticMap.get(state.getStatisticKey());
			
			if (!states.contains(state))
				i.remove();
		}
	}
	
	protected void matchTree4Word(List<Word> words) throws Exception
	{
		for (Word word : words)
		{
			List<LTAGTree> trees = new ArrayList<LTAGTree>();
			word.setTrees(trees);
			
			List<LTAGTree> list = ltagMap.get(word.getLexical());
			if (list != null)
			{
				trees.addAll(appendWord2LTAGTrees(list, word));
				continue;
			}
			
			list = ltagMap.get(word.getPos());
			if (list != null)
			{
				trees.addAll(appendWord2LTAGTrees(list, word));
				continue;
			}
			
			if (trees.size() == 0)
				throw new Exception("Can not find any super tree for the word :" + word.getLexical() + "/" + word.getPos());
		}
	}
	
	private List<LTAGTree> appendWord2LTAGTrees(List<LTAGTree> list, Word word)
	{
		List<LTAGTree> clonedTrees = new ArrayList<LTAGTree>();
		
		for (LTAGTree t : list)
		{
			if (!t.getAnchor().getNodeText().equalsIgnoreCase(word.getPos()))
				continue;
			
			LTAGTree clonedTree = t.clone();
			
			clonedTree.appendWord(word);
			clonedTree.setWordIndex(word.getWordIndex());
			
			clonedTrees.add(clonedTree);
		}
		
		return clonedTrees;
	}
	
	private List<List<LTAGTree>> findInitCandidateTrees(List<Word> words)
	{
		List<List<LTAGTree>> initCandidateTrees = new ArrayList<List<LTAGTree>>();
		
		for (int i = 0; i < words.size(); i++)
		{
			List<LTAGTree> wordCandidatetrees = new ArrayList<LTAGTree>();
			wordCandidatetrees.addAll(words.get(i).getTrees());
			
			initCandidateTrees.add(i, wordCandidatetrees);
		}
		
		return initCandidateTrees;
	}
	
	private List<LTAGState> findInitLTAGStateSet(List<Word> words, List<List<LTAGTree>> initCandidateTrees)
	{
		List<LTAGState> initStateSet = new ArrayList<LTAGState>();
		
		for (int i = 0; i < initCandidateTrees.size(); i++)
		{
			List<LTAGTree> trees = initCandidateTrees.get(i);
			if (trees == null)
				continue;
			
			for (int j = 0; j < trees.size(); j++)
			{
				LTAGTree tree = trees.get(j);
				
				if (tree.getType() != TreeType.I)
					continue;
				if (tree.getBeginCount() == 0)
					continue;
				if (!"IP".equalsIgnoreCase(tree.getRoot().getNodeText()))
					continue;
					
				LTAGState state = generateLTAGState(tree, null, 0);
				state.setId(stateCount.getAndIncrement());
				
				initStateSet.add(state);
			}
		}
		
		return initStateSet;
	}
	
	protected List<ParserTree> getParsedTree(List<LTAGState> matchedStates)
	{
		List<ParserTree> parserTrees = new ArrayList<ParserTree>();
		
		Set<String> parserTreeStrings = new HashSet<String>();
		
		if (matchedStates == null || matchedStates.size() == 0)
			logger.info("-------------NOT MATCHED---------");
		else
		{
			Collections.sort(matchedStates);
			
			logger.info("-------------MATCHED---------");
			logger.info(matchedStates);
			logger.info("-------------MATCHED STATE TRACE---------");
			
			for (int i = 0; i < matchedStates.size() && bestResutCount > 0; i++, bestResutCount--)
			{
				LTAGState matchedState = matchedStates.get(i);
				
				ParserTree parserTree = ParserTree.build(matchedState);
				
				logger.info(matchedState.toTrace());
				if (parserTreeStrings.add(parserTree.getTree().toLTAG()))
					parserTrees.add(parserTree);
				else
					logger.info("DUPLICATED");
			}
		}
		
		return parserTrees;
	}
	
	enum AdjunctType {NONE, ALL, ONLY_LEFT};
	
	private AdjunctType checkAdjunctType(LTAGState state, int step, int wordIndex)
	{
		if (step > wordIndex)
		{
			if (state.getNode().getLocation() == 0)
				return AdjunctType.ONLY_LEFT;
			else
				return AdjunctType.NONE;
		}
		
		return AdjunctType.ALL;
	}
	
	protected List<LTAGState> getAdjunctState(LTAGState state, int step)
	{
		List<LTAGState> newStates = new ArrayList<LTAGState>();
		
		int wordIndex = state.getTree().getWordIndex();
		int nearWordIndex = state.getNearWordIndex();
		int endStep = candidateTrees.size();
		int index = step;
		
		AdjunctType adjunctType = checkAdjunctType(state, step, wordIndex);
		if (adjunctType == AdjunctType.NONE)
			return newStates;
		
		if (index < wordIndex)
			endStep = wordIndex;
		else if (index < nearWordIndex)
			endStep = nearWordIndex;
		
		for (; index < endStep; index++)
		{
			List<LTAGTree> list = getCandidateTrees(state, index);
			if (list == null)
				continue;
			
			newStates.addAll(addCandidateTrees(state, list, TreeType.A, index, step, adjunctType));
		}
		
		if (filterBestCount > 0)
			filterStateSetByPossibiltiy(newStates);
		
		return newStates;
	}
	
	protected List<LTAGState> getSubstitutionState(LTAGState state, int step)
	{
		List<LTAGState> newStates = new ArrayList<LTAGState>();
		
		int wordIndex = state.getTree().getWordIndex();
		int nearWordIndex = state.getNearWordIndex();
		int endStep = candidateTrees.size();
		int index = step;
		
		if (wordIndex == step)
			return newStates;
		
		if (index < wordIndex)
			endStep = wordIndex;
		else if (index < nearWordIndex)
			endStep = nearWordIndex;
		
		for (; index < endStep; index++)
		{
			List<LTAGTree> list = getCandidateTrees(state, index);
			if (list == null)
				continue;
			
			newStates.addAll(addCandidateTrees(state, list, TreeType.I, index, step, null));
		}
		
		if (filterBestCount > 0)
			filterStateSetByPossibiltiy(newStates);
		
		return newStates;
	}
	
	private List<LTAGTree> getCandidateTrees(LTAGState state, int index)
	{
		if (state.getTree().getWordIndex() == index)
			return null;
		
		List<Operator> operators = state.getOperatorHistory();
		
		for (int i = 0; i < operators.size(); i++)
		{
			Operator operator = operators.get(i);
			
			if (i == 0 && operator.getTree1().getWordIndex() == index)
				return null;
			
			if (operator.getTree2().getWordIndex() == index)
				return null;
		}
		
		List<LTAGTree> candidates = new ArrayList<LTAGTree>();
		List<LTAGTree> trees = candidateTrees.get(index);
		
		candidates.addAll(trees);
		
		return candidates;
	}
	
	private List<LTAGState> addCandidateTrees(LTAGState state, List<LTAGTree> list, TreeType treeType, int index, int step, AdjunctType adjunctType)
	{
		List<LTAGState> newStates = new ArrayList<LTAGState>();
		LTAGNode node = state.getNode();
		int wordIndex = state.getTree().getWordIndex();
		String op = "$";
		
		if (TreeType.A == treeType)
			op = "*";
		
		for (int j = 0; j < list.size(); j++)
		{
			LTAGTree tree = list.get(j);
			
			if (treeType != tree.getType())
				continue;
			
			if (TreeType.A == treeType && wordIndex == step && tree.getAnchor().getLeafIndex() < tree.getFoot().getLeafIndex())
				continue;
			
			if (!tree.getRoot().getNodeText().equalsIgnoreCase(node.getNodeText()))
				continue;
			
			if (adjunctType == AdjunctType.ONLY_LEFT && tree.getLeafNodes().indexOf(tree.getFoot()) != 0)
				continue;
			
			if (TreeType.I == treeType && tree.getRoot().getSemanticTag() != null && !tree.getRoot().getSemanticTag().equalsIgnoreCase(node.getSemanticTag()))
				continue;
			
			Operator operator = getOperator(state.getTree(), tree, op, state.getNode());
			
			LTAGState newState = generateLTAGState(tree, state, step);
			
			newState.setPreviousState(state);
			newState.setParentState(state);
			newState.setOperatorHistory(state.cloneOperatorHistory());
			newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
			//newState.getOperatorHistory().add(operator);
			newState.addOperator(operator);
			
			if (!newState.validateOperator(words))
				continue;
			
			newState.setId(stateCount.getAndIncrement());
			newStates.add(newState);
		}
		
		return newStates;
	}
	
	private Operator getOperator(LTAGTree tree1, LTAGTree tree2, String op, LTAGNode tree1Node)
	{
		ArrayKey key = new ArrayKey(tree1, tree2, op, tree1Node);
		
		Operator operator = cacheOperator.get(key);
		
		if (operator == null)
		{
			operator = new Operator(tree1, tree2, op, tree1Node);
			cacheOperator.put(key, operator);
		}
		
		return operator;
	}
	
	protected boolean validateStatistic(LTAGState state, int best)
	{
		ArrayKey key = state.getStatisticKey();
		PriorityQueue<LTAGState> freqQueue = statisticMap.get(key);
		
		if (freqQueue == null)
		{
			freqQueue = new PriorityQueue<LTAGState>(best, new Comparator<LTAGState>()
					{
						@Override
						public int compare(LTAGState arg0, LTAGState arg1) 
						{
							return arg1.compareTo(arg0);
					}});
			statisticMap.put(key, freqQueue);
		}
		
		if (freqQueue.size() < best)
		{
			addStateToFreqQueue(freqQueue, state, best);
			return true;
		}
		
		LTAGState s = freqQueue.peek();
		
		if (s.compareTo(state) < 0)
			return false;
		
		addStateToFreqQueue(freqQueue, state, best);
		
		return true;
	}
	
	private void addStateToFreqQueue(PriorityQueue<LTAGState> freqQueue, LTAGState state, int best)
	{
		if (state.getOperatorHistory().size() > 0)
		{
			Iterator<LTAGState> i = freqQueue.iterator();
			
			while (i.hasNext())
			{
				if (state.operatorHistoryEquals(i.next()))
					return;
			}
		}
		
		freqQueue.add(state);
		
		if (freqQueue.size() <= best)
			return;
		
		freqQueue.remove();
	}
}
